7、积木画
题目 积木画
思路分析
画图找了一下规律 发现并没有什么公式的性质在
倒是体会到了一点dp的味道
然后尝试了一下好像真的可以
画图找规律 画了又擦 擦了又画 花了一个多小时吧 考试真心不建议做……
大概找到了个规律 所有的情况都会从前面已有的积木拼接而成 而1→2是会产生一个新拼法的（宽度增加 横着放变成一种可能） 2→3会增加两种新拼法（宽度增加 让放体积为3的积木成为可能 要拼满 3的积木需要成对出现 占据2*2的方格）3→4会增加两种新拼法(两长边衔接 宽为4） 然后后面应该就不会出现什么新的方法了 都可以从前面的积木组合而来 然后组合后的积木可以忽略不用它进行下一步组合 因为它一定可以被组合前的几种积木的组合替换
所以 大概就是 转变成了 （因为高固定 所以只有宽会变） 在宽度N的限制下 选以下这6种物品
每个物品可以选择多次 然后体积（宽度）不太一样 第一个宽1 第二个宽2 第三第四宽3
完全背包问题吗
但是怎么解决 1,2 2,1不是同一种的问题
……
找了一下别人的写法 也差不多分析到了这里
但是我方向跟他走岔了
代码实现
#include <stdio.h>
#define mod 1000000007
int main()
{
long long n = 0;
long long a, b, c, d;
a = 1，b = 1, c = 2;
scanf("%lld", &n);
for (int i = 3; i <= n; i++)
{
d = (c * 2 + a) % mod;
a = b;
b = c;
c = d;
}
printf("%lld", d);
return 0;
}
💬 评论